The Internet is a set of networks connected by routers. A router maintains a routing table that indicates for each possible destination network, the next hop to which a received data packet should be forwarded. The next hop may be another router or the final destination.
An Internet Protocol (xe2x80x9cIPxe2x80x9d) data packet received at a port in a router includes an IP destination address. The IP destination address is the final destination of the IP data packet. Currently there are two versions of IP, IP version 4 (xe2x80x9cIPv4xe2x80x9d) and IP version 6 (xe2x80x9cIPv6xe2x80x9d). IPv4 provides a 32-bit field in an IP header included in the data packeted for storing the IP destination address. The router forwards a received data packet connected to a next-loop router or the final destination if the destination is the local network, dependent on the IP destination address stored in the IP header.
A 32-bit IPv4 destination address provides 4 billion possible routes. An Internet router typically stores 50,000 of the 4 billion possible routes. However, the number of stored routes will increase with the growth of the Internet and the widespread use of IPv6.
Originally, the IP address space was divided into three classes of IP addresses; A, B and C. Each IP address space was divided into a network address and a host address. Class A allowed for 126 networks and 16 million hosts per network. Class B allowed for 16382 networks with 64,000 hosts per network and class C allowed for 2 million networks with 256 hosts per network. However, dividing the IP address space into different classes reduced the number of available IP addresses. Class C only allowed a maximum of 256 hosts per network which is too small for most organizations. Therefore, most organizations were assigned a Class B address, taking up 64,000 host addresses which could not be used by other organizations even if they were not used by the organization to which they were assigned. Hosts in an organization with a Class B IP address all store the same network address in the 16 Most Significant Bits (xe2x80x9cMBSsxe2x80x9d), for example, 128.32.xx.xx.
Classless InterDomain Routing (xe2x80x9cCIDRxe2x80x9d) was introduced to free up unused IP host addresses. The remaining unused networks are allocated to organization in variable sized blocks. An organization requiring 500 addresses gets 500 continuous addresses. For example, an organization can be assigned 500 available addresses starting at 128.32.xx. The number of routes stored by a router has increased since the introduction of Classless InterDomain Routing. Classless InterDomain Routing requires longest prefix matching to find the corresponding route instead of searching for a matching network address in order to find the corresponding next hop for the IP destination address. For example, a search can no longer stop after the 16 MSBs of a Class B IP address, for example, 128.xx.xx because 128.32.4.xx may be assigned to another organization requiring a different next hop.
One method for searching for a longest prefix match for a key is through the use of a binary tree search. A binary tree search matches a 32-bit input bit by bit down to 32 levels, requiring 32 searches to finding the entry matching the 32-bit key. Another method for searching for a match is through the use of a Patricia tree. A Patricia tree reduces the number of searches required if there are no entries down a leaf of the binary tree.
Yet another method for efficiently searching for a next hop associated with an IP destination address is described in PCT application Ser. No. PCT/SE98/00854 entitled xe2x80x9cMethod and System for Fast Routing Lookupsxe2x80x9d by Brodnick et al. filed on May 11, 1998. The method described by Brodnick reduces the number of next hops stored by not storing duplicate routes. By reducing the number of next hops, the memory requirement is reduced so that a route lookup table can be stored in fast cache memory.
Brodnick et al. divides the binary tree into 3-levels. Dividing the binary tree into 3-levels reduces the number of searches to three. The indexed entry in the first level indicates whether the search can end at the first level with the route taken from the entry, or the search must continue to a subsequent level using a further portion of the IP destination address.
FIG. 1A illustrates a prior art 64K (65536) bit map representing the first level of a binary tree. A 64K bit map 30 represents the leaves or nodes 44 of the binary tree at depth 16, with one bit per node 44. The bit map is divided into bit-masks of length 16. There are 212=4096 bit masks in the 64 k bit map. One bit mask is shown in FIG. 1A. A bit in the bit map 30 is set to xe2x80x981xe2x80x99 if there is a subtree or a route index stored in an array of pointers corresponding to the node 44. A bit in the bit map 30 is set to xe2x80x980xe2x80x99 if the node shares a route entry with a previous node 44.
FIG. 1B illustrates prior art lookup table implemented in cache memory. The lookup table includes an array of code words 36, an array of base indices 34 and a map table 40. A 32-bit IP address 38 is also shown in FIG. 1B. A codeword 46 is stored in the array of code words 36 for each bit mask in the bit map 30 (FIG. 1A). The code word 46 includes a six-bit value 46a and a 10-bit offset 46b. A base index 42 is stored in the array of base indices 34 for every four code words 46 in the array of code words 36.
The array of code words 36, array of base indices 34 and map table 40 are used to select a pointer in an array of pointers (not shown). The pointer stores a route index or an index to perform a further search.
A group of pointers in the array of pointers is selected by selecting a code word 46 in the array of code words 36 and a base index 42 in the array of base indices 34. The code word 46 is selected using the first 12 bits 50 of the IP address 38. The base index 42 is selected using the first 10 bits 48 of the IP address 38. The correct pointer in the group of pointers is selected using the map table 32.
The 10-bit value 46b in the selected code word 36 is an index into the map table 32. The map table 32 maps bit numbers within a bit-mask to 4-bit offsets. The offset specifies the pointer within the selected group of pointers in the array of pointers. The 10-bit value 46b selects the row in the map table 32 and bits 19:16 of the IP address 52 selects the 4-bit offset 54.
Thus, a search for a pointer requires the following cache memory accesses: (1) read a 16 bit code word 46; (2) read a 16-bit base address 42; (3) read a 4 bit offset 54 from the map table 32; (4) read a pointer at a pointer index where the pointer index is the sum of the base address 42, the code word offset 46a and the 4-bit offset 54.
The same memory accesses are required for each level of the binary tree. Thus, a search of three levels requires 12 memory accesses.
Throughput is limited by the cache memory""s bandwidth because the method described by Brodnick requires multiple searches of the route lookup table implemented in cache memory and each search requires multiple memory accesses of the cache memory.
In accordance with the invention a longest prefix match lookup table is presented. The lookup table includes a first level mapper and a second level mapper. The first level mapper includes a plurality of first memory locations indexed by a first portion of the key provided in a search request. The indexed entry indicates whether the search can end at the first mapper, with the route taken from the entry, or the search must continue to a subsequent mapper using a further portion of the key. The second memory mapper includes a plurality of second memory locations indexed based on a second portion of the key and a first subtree select stored in an indexed one of the first memory locations. A single search request issued to the lookup table results in a value corresponding to the key stored in a location in one of the mappers.
The second level mapper includes a subtree memory, a subtree mapper and mapper address logic. The a subtree memory stores a subtree descriptor indexed by the subtree select. The subtree mapper includes the second memory locations and the mapper address logic provides a mapper index for the subtree mapper dependent on the selected subtree descriptor and the second portion of the key.
The subtree descriptor includes a bit map and block pointers. The bit map includes a bit for each possible node in the subtree. The block pointers store a base address of a block of second memory locations for storing the value.
A bit in the bit map corresponding to the node set to xe2x80x980xe2x80x99 indicates the node shares a value with the previous node. The index for the second memory location is dependent on the number of xe2x80x981xe2x80x99s stored in the bit map prior to the bit corresponding to the node. The number of values stored in the mapper for the subtree is dependent on the number of xe2x80x981xe2x80x99s stored in the bit map. The block may include 16 second memory locations and the number of possible nodes may be 256.
In one embodiment, the lookup table may include a third level mapper comprising a plurality of third memory locations indexed dependent on a third portion of the key and a second subtree select stored in one of the second memory locations. The key is 32 bits, the first portion of the key is 16 bits, the second portion of the key is 8 bits and the third portion of the key is 8 bits.
In another embodiment, the lookup table may include a fourth level mapper including a plurality of fourth memory locations indexed dependent on a fourth portion of the key and a third subtree select stored in one of the third memory locations where the key is 40 bits, the first portion of the key is 16 bits, the second portion of the key is 8 bits, the third portion of the key is 8 bits and the fourth portion of the key is 8 bits.